package 牛客.链表;

import 剑指offer.ListNode;

public class BM8链表中倒数最后k个结点 {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        //双指针
        //第一个指针先走k步后，两个指针一起走，当第一个指针为空时，第二指针指向的就是倒数第K个节点
        ListNode p=pHead;
        ListNode q=pHead;
        int n=0;
        while (p!=null) {
            if (n<k) {
                p=p.next;
                n++;
            }else {
                //n==k
                q=q.next;
                p=p.next;
            }
        }

        if (n<k) {
            return null;
        }
        return q;
    }

    public ListNode FindKthToTail1 (ListNode pHead, int k) {
        // write code here
        int size=0;
        ListNode cur=pHead;
        while(cur!=null) {
            size++;
            cur=cur.next;
        }
        if(size<k) {
            return null;
        }
        cur=pHead;
        for(int i=0;i<size-k;i++) {
            cur=cur.next;
        }
        return cur;

    }
}
